package org.bear.array;

public class NumMatrix {
    private int[][] matrix;

    private int[][] sumMat;


    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
        sumMat = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            sumMat[i][0] = matrix[i][0];
            for (int j = 1; j < matrix[i].length; j++) {
                sumMat[i][j] = sumMat[i][j-1] + matrix[i][j];
            }
        }
    }

//    计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int res = 0;
        for(int i=row1;i<=row2;i++){
            res += sumMat[i][col2];
            if (col1>0){
                res -= sumMat[i][col1-1];
            }
        }
        return res;
    }


    public static void main(String[] args) {
        NumMatrix numMatrix = new NumMatrix(new int[][]{{3,0,1,4,2}, {5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}});
        System.out.println(numMatrix.sumRegion(2,1,4,3));
    }
}
